package algorithm.t202110;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/16 10:14
 * @description : 3道
 */
public class t20211016 {


    //3.无重复字符的最长子串 滑动窗口
    static public int lengthOfLongestSubstring(String s) {
        if (s == null) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        HashMap<Character, Integer> map = new HashMap<>();

        int slow = 0;
        int max = 0;
        int fast = 0;

        for (; fast < s.length(); fast++) {

            if (map.containsKey(s.charAt(fast))) {
                max = Math.max(max, fast - slow);
                if (map.get(s.charAt(fast)) >= slow) {
                    slow = map.get(s.charAt(fast)) + 1;
                    map.put(s.charAt(fast), fast);
                }

            }

            map.put(s.charAt(fast), fast);

        }

        max = Math.max(max, fast - slow);

        return max;

    }


    //567.字符串的排列 滑动窗口
    static public boolean checkInclusion(String s1, String s2) {
        if (s1.length() == 1 && s1.length() == s2.length()) {
            return s1.equals(s2);
        }

        if (s1.length() == 1) {
            return s2.contains(s1);
        }

        char[] son = new char[123];
        char[] father = new char[123];

        //将s1放入偏移数组
        for (int i = 0; i < s1.length(); i++) {
            son[s1.charAt(i)]++;
        }

        //获取son的长度，用于滑动窗口
        int len = s1.length();

        //开始遍历father
        father[s2.charAt(0)]++;
        for (int slow = 0, fast = 1; fast < s2.length(); fast++) {

            if (fast - slow > len - 1) {
                father[s2.charAt(slow)]--;
                father[s2.charAt(fast)]++;
                slow++;
            } else {

                father[s2.charAt(fast)]++;
            }


            if (Arrays.equals(son, father)) {
                return true;
            }


        }

        return false;
    }


    //面试题02.08 环路检测
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }

        if (head.next == null) {
            return null;
        }


        HashMap<ListNode, ListNode> map = new HashMap<>();

        map.put(head, head);

        ListNode temp = head;//辅助指针

        while (true) {
            if (temp.next == null) {
                return null;
            }
            if (map.containsKey(temp.next.next)) {
                return map.get(temp.next.next);
            }
            map.put(temp.next, temp.next);
            temp = temp.next;
        }


    }

    //面试题02.09 栈的最小值


    public static void main(String[] args) {

        TreeSet<String> treeSet = new TreeSet<>();


        MyStack stack = new MyStack(4);

        stack.push(1);
        stack.push(2);
        stack.push(3);


    }
}

class MyStack {

    int[] arr;
    int front = 0;//栈底
    int near = -1;//栈顶


    public MyStack(int capacity) {
        arr = new int[capacity];
    }

    public void push(int element) {
        //判断栈是否已经满了
        if (isFull()) {
            System.out.println("栈已满");
            return;
        }


        near = (near + 1) % arr.length;
        arr[near] = element;

    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("栈为空，弹不出来东西");
            return -1;
        }
        int res = arr[near];
        front = front + 1 % arr.length;

        return res;
    }

    public boolean isFull() {//判断栈是否已经满了
        return near + 1 % arr.length == front;
    }

    public boolean isEmpty() {
        return front > near;
    }


}